# 初始状态和目标状态
import copy
import time

initial = [
    [5, 1, 2, 4],
    [9, 6, 3, 8],
    [13, 15, 10, 11],
    [14, 0, 7, 12]
]
goal = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 0]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def find_site(state, element):  # 返回0即空格的位置
    for i in state:
        for j in i:
            if j == element:
                return state.index(i), i.index(j)


def print_state(state):  # 可视化输出
    for i in state:
        print(f'{i[0]}\t{i[1]}\t{i[2]}\t{i[3]}')
    print()


def print_path(Close):
    path = []
    tmp = Close[-1]
    while tmp[2] != -1:
        path.append(Close[tmp[2]][0])
        tmp = Close[tmp[2]]
    path.reverse()
    print(f'A*算法求解十五数码如下: ')
    for i in path:
        print_state(i)
        print('↓')
    print_state(goal)
    print(f'长度为 {len(path)}, 总试探步数 {len(Close) - 1}, ', end='')


def mhd_distance(state1, state2):
    distance = 0
    for i in state1:
        for j in i:
            site1 = find_site(state1, j)
            site2 = find_site(state2, j)
            distance = distance + abs(site1[0] - site2[0]) + abs(site1[1] - site2[0])
    return distance


def AStar():
    visited = [initial]
    Open = [(initial, 0, -1, 0, 0)]
    Close = [(initial, 0, -1, 0, 0)]
    # 五元组：状态、当前节点下标、父节点下标、到当前状态移动的次数、静态估计值
    while Open:
        Open.sort(key=lambda x: x[4])  # 按照静态估计值排列Open中节点，出队静态估计值最小的
        cur = Open.pop(0)
        cx, cy = find_site(cur[0], 0)  # 返回0(空格)在当前状态(嵌套列表)中的索引
        for dir in dirs:
            tx = cx + dir[0]
            ty = cy + dir[1]
            if 0 <= tx < 4 and 0 <= ty < 4:  # 移动后是否出界
                tmp = copy.deepcopy(cur[0])  # 需要这么拷贝!
                # 0与相邻位置的数字交换位置，得到新的状态
                tmp[tx][ty], tmp[cx][cy] = tmp[cx][cy], tmp[tx][ty]
                if tmp not in visited:  # 移动后的状态是否扩展过
                    f = cur[3] + mhd_distance(tmp, goal)  # 计算节点的静态估计值
                    visited.append(tmp)  # 新状态加入 visited、Open、Close
                    Open.append((tmp, len(Close), cur[1], cur[3] + 1, f))
                    Close.append((tmp, len(Close), cur[1], cur[3] + 1, f))
                    if tmp == goal:  # 如果是目标状态，直接输出求解过程，结束算法
                        print_path(Close)
                        return


start_time = time.perf_counter()
AStar()
end_time = time.perf_counter()
runtime = end_time - start_time
print(f' 运行时间 {runtime}')
